CF1263E Editor

难度不大，比较有意思的一道思维题

题解：

首先是括号序列的经典操作：将左括号看作1，将右括号看作-1

按照该操作，显然的，合法的括号序列的前缀应该都是大于等于0的，且总和等于0

换句话说，若要判断当前括号序列是否合法，就要知道它的最小前缀是否小于0，是则不合法；还要知道总和是否等于0，否则不合法

在合法的基础上，概括号序列的最大深度就是最大前缀

数字和，前缀最大，前缀最小

将上面三样东西拿线段树维护一下就解决问题了

另外，对于字符的修改，在线段树上的表现就是单点赋值（1/-1/0）

由于只有全局查询，甚至都不用写query函数

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e6+5;
int n,a[N<<2],mi[N<<2],ma[N<<2];
char s[N];

void pushup(int x){
    a[x]=a[x<<1]+a[x<<1|1];
    mi[x]=min(mi[x<<1],a[x<<1]+mi[x<<1|1]);
    ma[x]=max(ma[x<<1],a[x<<1]+ma[x<<1|1]);
}

void up(int x,int l,int r,int p,int v){
    if(l==r){
        a[x]=mi[x]=ma[x]=v;
        return ;
    }
    int mid=l+r>>1;
    if(p<=mid) up(x<<1,l,mid,p,v);
    else up(x<<1|1,mid+1,r,p,v);
    pushup(x);
}

signed main(){
    read(n);
    scanf("%s",s+1);
    for(int i=1,pos=1;i<=n;i++){
        if(s[i]=='L') pos-=(pos>1);
        else if(s[i]=='R') pos++;
        else{
            if(s[i]=='(') up(1,1,n,pos,1);
            else if(s[i]==')') up(1,1,n,pos,-1);
            else up(1,1,n,pos,0);
        }
        if(a[1]||mi[1]<0) write(-1);
        else write(ma[1]);
        putchar(' ');
    }
}